package done.normal_601_700;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 662. 二叉树最大宽度
 * Example 4：
 * Input:
 * 1
 * /           \
 * 3               2
 * /     \        /     \
 * 5      nil     nil      9
 * /\     /  \    /  \    /  \
 * 6 nil  nil nil nil nil nil  7
 * <p>
 * Output: 8 => {6, nil, nil, nil, nil, nil, nil, 7}
 *
 * @author 大硕
 * 2019-03-20 7:34 AM
 **/
@Slf4j
public class MaximumWidthOfBinaryTree {

    @SuppressWarnings("all")
    public int widthOfBinaryTree(TreeNode root) {
        //190320 first
        return 0;
    }

    @Test
    public void test() {
        TreeNode root;
        root = new TreeNode(1,
                new TreeNode(3,
                        new TreeNode(5,
                                new TreeNode(6))),
                new TreeNode(2,
                        null, new TreeNode(9,
                        null, new TreeNode(7))));
        log.info("result:{}", widthOfBinaryTree(root));
    }
}




























/*
private int maxW = 0;

*/
/**
 * 假设满二叉树表示成数组序列, 根节点所在的位置为1, 则任意位于i节点的左右子节点的 index为2*i, 2*i+1
 * 用一个List保存每层的左端点, 已知二叉树有多少层List的元素就有多少个.
 * 那么可以在dfs的过程中记录每个节点的index及其所在的层level,
 * 如果level > List.size()说明当前节点就是新的一层的最左节点,
 * 将其加入List中, 否则判断当前节点的index减去List中对应层的最左节点的index的
 * 宽度是否大于最大宽度并更新 Math.max()
 **//*

@SuppressWarnings("all")
public int widthOfBinaryTree(TreeNode root) {
    //NO.1 根节点传入递归循环
    dfs(root, 1, 1, new ArrayList<Integer>());
    return maxW;
}

private void dfs(TreeNode r, int level, int index, List<Integer> left) {
    if (r == null) {
        return;
    }

    if (level > left.size()) {
        left.add(index);
    }

    // 更新当前最大深度值                            List 队列, 二叉树有多深就有多少个元素
    //                     1                        ||  1 层  level = 1,
    //               /          \                   ||
    //             i             i+1                ||  2 层  level
    //         /     \          /    \              ||
    //       (2i)    (2i+1)  (2i+2)  (2i+3)         ||  3 层
    //       /  \       \               \           ||
    //    (4i) (4i+1)  (4i+3)          (4i + 7)     \/  4 层
    //
    maxW = Math.max(maxW, index - left.get(level-1) + 1);

    //NO.1 左子树计算最大深度
    dfs(r.left, level+1, index*2, left);

    //NO.2 右子树计算最大深度
    dfs(r.right, level+1, index*2+1, left);
}
*/
